/*
 * @Author: liusheng
 * @Date: 2022-06-11 12:14:56
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-12 17:25:01
 * @Description: 剑指 Offer II 077. 链表排序
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 * 剑指 Offer II 077. 链表排序
给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

 

示例 1：



输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：



输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：

输入：head = []
输出：[]
 

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
 

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？


/**
 * @brief merge sort from top to bottom.time:O(nlogn),space:O(nlogn)
 * 
 */

struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sortList(head,nullptr);
    }

    ListNode * sortList(ListNode * head,ListNode * tail)
    {
        if (head == nullptr)
        {
            return head;
        }

        if (head->next == tail)
        {
            head->next = nullptr;
            return head;
        }
        ListNode * slow = head;
        ListNode * fast = head->next;
        while (fast != tail)
        {
            slow = slow->next;
            fast = fast->next;
            if (fast != tail)
            {
                fast = fast->next;
            }
        }

        ListNode * mid = slow;
        ListNode * secondHead = mid->next;
        head = sortList(head,mid);
        secondHead = sortList(mid,tail);
        return merge(head,secondHead);
    }

    ListNode * merge(ListNode * head1,ListNode * head2)
    {
        ListNode * dummyHead = new ListNode();
        ListNode * newHead = dummyHead;
        while (head1 && head2)
        {
            if (head1->val < head2->val)
            {
                newHead->next = head1;
                head1 = head1->next;
                newHead = newHead->next;
            }
            else
            {
                newHead->next = head2;
                head2 = head2->next;
                newHead = newHead->next;
            }
        }

        if (head1)
        {
            newHead->next = head1;
        }

        if (head2)
        {
            newHead->next = head2;
        }

        newHead = dummyHead->next;
        delete dummyHead;
        return newHead;
    }
};

/**
 * @brief merge sort from bottom to top.time:O(nlogn),space:O(nlogn)
 * 
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        int totalLength = listLength(head);
        ListNode * dummyHead = new ListNode(0,head);
        ListNode * prev = dummyHead;
        for (int sortLength = 1; sortLength < totalLength; sortLength <<= 1)
        {
            prev = dummyHead;
            ListNode * cur = prev->next;
            while (cur)
            {
                ListNode * head1 = cur;
                //cur->next ensure that it has successor
                for (int i = 1; cur->next && i < sortLength; ++i)
                {
                    cur = cur->next;
                }

                ListNode * head2 = cur->next;
                cur->next = nullptr;
                cur = head2;

                for (int i = 1; cur && i < sortLength; ++i)
                {
                    cur = cur->next;
                }

                ListNode * next = nullptr;
                if (cur)
                {
                    next = cur->next;
                    cur->next = nullptr;
                }
                
                ListNode * merged = merge(head1,head2);
                prev->next = merged;
                while (prev->next)
                {
                    prev = prev->next;
                }
                cur = next;
            }
        }

        ListNode * newHead = dummyHead->next;
        delete dummyHead;

        return newHead;
    }

    int listLength(ListNode * head)
    {
        int length = 0;
        while (head)
        {
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode * merge(ListNode * head1,ListNode * head2)
    {
        ListNode * dummyHead = new ListNode();
        ListNode * newHead = dummyHead;
        while (head1 && head2)
        {
            if (head1->val < head2->val)
            {
                newHead->next = head1;
                head1 = head1->next;
                newHead = newHead->next;
            }
            else
            {
                newHead->next = head2;
                head2 = head2->next;
                newHead = newHead->next;
            }
        }

        if (head1)
        {
            newHead->next = head1;
        }

        if (head2)
        {
            newHead->next = head2;
        }

        newHead = dummyHead->next;
        delete dummyHead;
        return newHead;
    }
};
